#define _CRT_SECURE_NO_WARNINGS

#include"tree.h"
#include"queue.h"

void prev_order(BTnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	prev_order(root->left);
	prev_order(root->right);
}

void in_order(BTnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	in_order(root->left);
	printf("%c ", root->data);
	in_order(root->right);
}

void post_order(BTnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	post_order(root->left);
	post_order(root->right);
	printf("%c ", root->data);
}

int tree_size(BTnode* root)
{
	return root == NULL ? 0 : tree_size(root->left) + tree_size(root->right) + 1;
}

int tree_leaf_size(BTnode* root)
{
	if (root == NULL)
		return 0;
	else if (root->left == NULL && root->right == NULL)
		return 1;
	else
		return tree_leaf_size(root->left) + tree_leaf_size(root->right);
}

void level_order(BTnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	queue q;
	queue_init(&q);
	queue_push(&q, root);
	while (!queue_empty(&q))
	{
		BTnode* front = queue_front(&q);
		queue_pop(&q);
		printf("%c ", front->data);
		if (front->left)
			queue_push(&q, front->left);
		if (front->right)
			queue_push(&q, front->right);
	}
	printf("\n");
	queue_destory(&q);
}

static void destory(BTnode* root)
{
	if (root == NULL)
	{
		return;
	}
	destory(root->left);
	destory(root->right);
	free(root);
}

void destory_tree(BTnode** proot)
{
	destory(*proot);
	*proot = NULL;
}
